package problem167;

//167. 两数之和 II - 输入有序数组
//https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150

//二分解法

class Solution2 {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for(int i = 0; i<n; i++) {
            int x = target-numbers[i];
            int index = binarySearch(numbers, i+1, n-1, x);
            if(index != -1) return new int[]{i+1, index+1};
        }
        return new int[]{-1,-1};
    }

    private int binarySearch(int[] num, int left, int right, int target) {
        if(left > right) return -1;
        while(left < right) {
            int mid = left + (right-left)/2;
            if(num[mid] < target) {
                left = mid+1;
            }else {
                right = mid;
            }
        }
        if(num[left] == target) return left;
        else return -1;
    }
}